#递归实现深度优先遍历
def dfs_recurse(v,g,visited=[]):
    if v in visited:
        return
    else:
        visited.append(v)
        for i in g[v]:
            dfs_recurse(i,g,visited)
    return visited

#栈的方式实现深度优先遍历
def dfs_stack(g,start_vertex):
    s=[start_vertex]
    visited=[]
    while len(s)>0:
        v=s.pop(-1)
        if v in visited:
            continue
        else:
            visited.append(v)
            s.extend(g[v])
    return visited
g={'a':['b','c'],
   'b':['c','d'],
   'c':['e','f'],
   'd':['g'],
   'e':['g'],
   'f':[],
   'g':[]
   }
def test():
    print('递归实现',dfs_recurse('a',g))
    print('栈实现',dfs_stack(g,'a'))
if __name__ == '__main__':
    test()